#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define MAXSIZE 30 //用于多序创建二叉树

typedef struct BiTNode
{
    char data;                       //结点数据域
    struct BiTNode *lchild,*rchild;  //左右孩子指针
}BiTNode,*BiTree;

typedef struct SqQueue
{
    int *base;
    int front;
    int rear;
}SqQueue;

int count=0;
int main()
{
    BiTree T;               //T表示指向根节点的指针

    void CreateBiTree(BiTree *T);
    BiTree Pre_InCreateBiTree(char *pre,char *in,int len);
    BiTree In_PosCreateBiTree(char *pos,char *in,int len);
    void PreOrderTraverse(BiTree T);
    void InOrderTraverse(BiTree T);
    void PosOrderTraverse(BiTree T);
    void LevelOrderTraverse(BiTree T);
    int NodeCount(BiTree T);
    int NodeCountChild(BiTree T);
    int NodeCountOnly(BiTree T);
    int NodeCountParent(BiTree T);
    int Depth(BiTree T);
    int TreeCompare(BiTree T,BiTree G);
    void TreeExchange(BiTree T);
    int FindWidth(BiTree T,int level);
    int MaxWidth(BiTree T);

    int len,temp,mode=100;
    char pre[MAXSIZE],in[MAXSIZE],pos[MAXSIZE];
    printf("---------------万恶的树功能菜单---------------\n");
    printf("【1】前序补空建树  【2】先序中序建树  【3】中序后序建树\n");
    printf("【A】前序层序建树  【B】中序层序建树  【C】后序层序建树\n");       
    printf("【4】先序输出  【5】中序输出  【6】后序输出  【7】层序输出\n");
    printf("【8】统计结点个数  【9】统计叶子结点个数  【10】统计度为1结点结束  【11】统计度为2结点个数\n");
    printf("【12】计算树的高度  【13】比较两棵树   【14】交换左右孩子   【15】计算最大宽度  【0】退出系统");
    while(mode!=0)
    {
        printf("\n请输入你想要的功能:");
        scanf("%d",&mode);
        getchar();
        if(mode==0)  break;
        switch(mode)
        {
            case 1:
            {
                printf("请输出先序遍历序列，空结点请补#:");
                CreateBiTree(&T);
                break;
            }
            case 2:
            {
                printf("请输入先序序列：");
                scanf("%s",pre);
                printf("请输入中序序列：");
                scanf("%s",in);
                len=strlen(in);
                T=Pre_InCreateBiTree(pre,in,len);
                break;
            }
            case 3:
            {
                printf("请输入后序序列：");
                scanf("%s",pos);
                printf("请输入中序序列：");
                scanf("%s",in);
                len=strlen(in);
                T=In_PosCreateBiTree(pos,in,len);
                break;
            }
            case 4:
            {
                printf("先序遍历结果是:");
                PreOrderTraverse(T);
                break;
            }
            case 5:
            {
                printf("中序遍历结果是:");
                InOrderTraverse(T);
                break;
            }
            case 6:
            {
                printf("中序遍历结果是:");
                PosOrderTraverse(T);
                break;
            }
            case 7:
            {
                printf("层序遍历结果是：");
                LevelOrderTraverse(T);
                break;
            }
            case 8:
            {
                count=0;
                temp=NodeCount(T);
                printf("结点个数是%d",temp);
                break;
            }
            case 9:
            {
                count=0;
                temp=NodeCountChild(T);
                printf("叶子结点个数是%d",temp);
                break;
            }
            case 10:
            {
                count=0;
                temp=NodeCountOnly(T);
                printf("度为1的结点个数是%d",temp);
                break;
            }
            case 11:
            {
                count=0;
                temp=NodeCountParent(T);
                printf("度为2的结点个数是%d",temp);
                break;
            }
            case 12:
            {
                temp=Depth(T);
                printf("树的高度为%d",temp);
                break;
            }
            case 13:
            {
                BiTree G;
                printf("请输出先序遍历序列，空结点请补#:");
                CreateBiTree(&G);
                temp=TreeCompare(T,G);
                if(temp==1)          printf("两棵树相等");
                else                 printf("两棵树不相等");
                break;
            }
            case 14:
            {
                TreeExchange(T);
                printf("交换完成");
                break;
            }
            case 15:
            {
                temp=MaxWidth(T);
                printf("树的宽度为%d",temp);
                break;
            }
        }
    }  
}

void CreateBiTree(BiTree *T)            //先序创建二叉树
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
    {
        (*T)=NULL;
    }
    else
    {
        *T=(BiTree)malloc(sizeof(BiTNode)); 
        (*T)->data=ch; 
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

void PreOrderTraverse(BiTree T)      //先序遍历
{
    if(T)
    {
        printf("%c",T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}

void InOrderTraverse(BiTree T)       //中序遍历
{
    if(T)
    {
        InOrderTraverse(T->lchild);
        printf("%c",T->data);
        InOrderTraverse(T->rchild);
    }
}

void PosOrderTraverse(BiTree T)      //后序遍历
{
    if(T)
    {
        PosOrderTraverse(T->lchild);
        PosOrderTraverse(T->rchild);
        printf("%c",T->data);
    }
}

void LevelOrderTraverse(BiTree T)
{
	int front,rear;
	front=rear=0;
	BiTree SqQueue[10];            //构造一个大小为10的简单循环队列，存储各结点的指针
	if(T!=NULL)
	{
		rear=(rear+1)%10;
		SqQueue[rear]=T;           //当前树/子树头结点入队
		while (rear!=front)
		{
			front=(front+1)%10;                     //当前树/子树头结点出队
			printf("%c",SqQueue[front]->data);      //出队时进行输出或进行操作
			if (SqQueue[front]->lchild!=NULL)
			{
				rear=(rear+1)%10;
				SqQueue[rear]=SqQueue[front]->lchild;
			}
			if (SqQueue[front]->rchild!= NULL)
			{
				rear=(rear+1)%10;
				SqQueue[rear]=SqQueue[front]->rchild;
			}
		}
	}
}

int NodeCount(BiTree T)
{
    if(T==NULL)   return 0;
    else          return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

int NodeCountChild(BiTree T)
{
    if(T==NULL)  return 0;
    else
    {
        if(T->lchild==NULL && T->rchild==NULL)  return 1;   
        //这个地方写成return NodeCountChild(T->lchild)+NodeCountChild(T->rchild)+1也一样
        return NodeCountChild(T->lchild)+NodeCountChild(T->rchild);
    }
}

int NodeCountOnly(BiTree T)
{
    if(T==NULL)  return 0;
    else
    {
        if((T->lchild==NULL && T->rchild!=NULL)|| (T->rchild==NULL &&T->lchild!=NULL))   return 1;
        else return NodeCountOnly(T->lchild)+NodeCountOnly(T->rchild);
    }
}

int NodeCountParent(BiTree T)
{
    if(T==NULL)    return 0;
    else
    {
        if(T->lchild!=NULL && T->rchild!=NULL)  return 1;
        else return NodeCountParent(T->lchild)+NodeCountParent(T->rchild);
    }
}

int Depth(BiTree T)
{
    int m,n;
    if(T==NULL)  return 0;
    else
    {
        m=Depth(T->lchild); 
        n=Depth(T->rchild); 
        if(m>n)   return(m+1);
        else      return(n+1);
    }
}

int TreeCompare(BiTree T,BiTree G)
{
    if(T==NULL&&G==NULL)   return 1;
    if((T!=NULL&&G==NULL) || (T==NULL&&G!=NULL))  return 0;
    if(T->data==G->data)
    {
        if(TreeCompare(T->lchild,G->lchild)&&TreeCompare(T->rchild,G->rchild))  return 1;
    }
    return 0;
}

/*这种方法调试时可以直接看到过程，但*和&的多次使用容易写错
int TreeExchange(BiTree *T)
{
    if((*T)==NULL) return 0;
    if(((*T)->lchild==NULL) && ((*T)->rchild==NULL))  return 0;
    BiTree *tempnode=(*T)->lchild;
    (*T)->lchild=(*T)->rchild;
    (*T)->rchild=tempnode;
    TreeExchange(&((*T)->lchild));
    TreeExchange(&((*T)->rchild));
}
*/

void TreeExchange(BiTree T)   //使用这种方法调试时手动添加监视*T
{
    if(T==NULL) return;
    if(T->lchild==NULL && T->rchild==NULL) return;
    //if(T->lchild!=NULL) && (T->rchild!=NULL)这里不能加上这个
    //上面这个if判断语句要是写了的话就忽略了只有一侧有结点的情况
    BiTree tempnode=T->lchild;
    T->lchild=T->rchild;
    T->rchild=tempnode;
    TreeExchange(T->lchild);
    TreeExchange(T->rchild);
}

int FindWidth(BiTree T,int level)
{
    if(T==NULL)  return 0;
    else
    {
        if(level==1)  return 1;
        else          return FindWidth(T->lchild,level-1)+FindWidth(T->rchild,level-1);
    }
}

int MaxWidth(BiTree T)
{
    int max=0;    //最大宽度
    int width=0;  //当前宽度
    int h=Depth(T);//深度
    for(int i=1;i<=h;i++)
    {
        width=FindWidth(T,i);
        if(max<width)  max=width;
    }
    return(max);
}

BiTree Pre_InCreateBiTree(char *pre,char *in,int len)
{
    if(len==0)    return NULL;
    char ch=pre[0];
    int index=0;
    while(in[index]!=ch)
    {
        index++;
    }
    BiTree T=(BiTree)malloc(sizeof(BiTNode));
    T->data=ch;
    T->lchild=Pre_InCreateBiTree(pre+1,in,index);  //创建左子树
    T->rchild=Pre_InCreateBiTree(pre+index+1,in+index+1,len-index-1); //创建右子树
    return T;
}

BiTree In_PosCreateBiTree(char *pos,char *in,int len)
{
    if(len==0)   return NULL;
    char ch=pos[len-1];
    int index=0;
    while(in[index]!=ch)
    {
        index++;
    }
    BiTree T=(BiTree)malloc(sizeof(BiTNode));
    T->data=ch;
    T->lchild=In_PosCreateBiTree(pos,in,index);  //创建左子树
    T->rchild=In_PosCreateBiTree(pos+index,in+index+1,len-index-1); //创建右子树
    return T;
}